本篇同步發布於Blog: [解題] LeetCode - 136 Single Number

平台：

LeetCode

題號：

136 - Single Number

題目連結：

https://leetcode.com/problems/single-number/

題目說明：

輸入一個不為空的陣列，每個整數的出現次數只有1個會是1次，其他都是出現2次，求那個只出現一次的整數值。

比如範例輸入[2,2,1]，只出現1次的是1，所以輸出1。

題目要求要線性時間、並不能用額外的記憶體空間。

解題方法：

需用到bit運算，有提示其他數字都是出現2次，代表這些數字對自己做XOR一定會是0。所以XOR最終的結果就是那個只出現1次的數字。

比如[3,2,1,2,3]，初始化ans = 0

1. ans = ans(00) ^ 3(11) = 3(11)
2. ans = ans(11) ^ 2(10) = 2(01)
3. ans = ans(01) ^ 1(01) = 0(00)
4. ans = ans(00) ^ 2(10) = 2(10)
5. ans = ans(10) ^ 3(11) = 1(01)

所以會是1

難度為Easy

程式碼 (C++ 與 C#)：

#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0 ; i < nums.size();++i){
            ans ^= nums[i];
        }
        
        return ans;
    }
};

int main() {
	
	vector<int> nums{1,2,4,4,2};
	Solution sol;
	cout << sol.singleNumber(nums) << endl;
	return 0;
}

using System;

namespace LeetCode136
{
    public class Solution
    {
        public int SingleNumber(int[] nums)
        {
            int ans = 0;
            foreach (int num in nums)
            {
                ans ^= num;
            }

            return ans;
        }
    }
    class Program
    {
        static void Main(string[] args)
        {
            int[] nums = new int[5]{1,2,4,4,2};
            Console.WriteLine(new Solution().SingleNumber(nums));
            Console.Read();
        }
    }
}

GITHUB位置(C++ 與 C#)：

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%2B%2B/100-199/136.cpp

https://github.com/u8989332/ProblemSolving/blob/master/LeetCode/C%23/100-199/136.cs